package solution.s_143;

/**
 * 解题思路：
 *      首先计算链表有多少个元素，比如链表为 1->2->3->4，共 4 个元素
 *      然后从中间拆分成两个链表，拆分的时候，第二个元素的 next 为空，从第三个元素开始使用逆序组成一个新的链表。
 *      最后将两个链表进行拼接。
 */
public class Solution20201020 {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) { return; }

        // 计算链表元素个数
        ListNode p = head;
        int elementNum = 0;
        while (p != null) {
            elementNum ++;
            p = p.next;
        }

        // 拆分两个链表
        ListNode ln1 = head;
        p = head;
        for (int i = 2; i <= (elementNum - 1) / 2 + 1; i ++) {
            p = p.next;
        }

        // 右边的链表
        ListNode originalList2 = p.next;
        // 左边的链表结束
        p.next = null;

        // 对右边的链表进行反向处理
        ListNode ln2 = null;
        while (originalList2 != null) {
            ListNode curNode = originalList2;
            originalList2 = originalList2.next;

            ListNode tmpNode = ln2;
            ln2 = curNode;
            ln2.next = tmpNode;
        }

        // 合并两个链表（使用虚拟头结点）
        head = new ListNode();
        p = head;
        while (ln1 !=  null || ln2 != null) {
            if (ln1 != null) {
                ListNode curNode = ln1;
                ln1 = ln1.next;

                curNode.next = null;
                p.next = curNode;
                p = p.next;
            }

            if (ln2 != null) {
                ListNode curNode = ln2;
                ln2 = ln2.next;

                curNode.next = null;
                p.next = curNode;
                p = p.next;
            }
        }

        // 去掉虚拟头结点
        head = head.next;
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
